I'm writing a sokoban solver for fun and practice, it uses a simple algorithm (something like BFS with a bit of difference).

now i want to estimate its running time ( O and omega). but need to know how to calculate count of acyclic paths from a vertex to another in a network. actually I want an expression that calculates count of valid paths, between two vertices of a m*n matrix of vertices.

a valid path:

• visits each vertex 0 or one times.
• have no circuits

for example this is a valid path:

but this is not:

What is needed is a method to find count of all acyclic paths between the two vertices a and b.

comments on solving methods and tricks are welcomed.